package arithmetic.LeetCode.Best_Time_to_Buy_and_Sell_Stock_III;

/**
 * @author zhangyanqi
 * @since 1.0 2017/10/17
 */
public class Solution {

    public int maxProfit(int[] prices) {
        if(prices.length == 0 || prices.length == 1){
            return 0;
        }
        int[] left = new int[prices.length];
        left[0] = 0;
        int[] right = new int[prices.length];
        right[prices.length -1] = 0;
        //从左开始到最后,计算最大利润
        int min = prices[0]; //最小的值
        for (int i = 1; i < prices.length; i++) {
            left[i] = Math.max(left[i - 1], prices[i] - min);
            min = Math.min(prices[i], min);
        }
        //从右开始到开头,计算最大利润
        int max = prices[prices.length - 1];
        for (int i = prices.length - 2; i > 0; i--) {
            right[i] = Math.max(right[i + 1], max - prices[i]);
            max = Math.max(prices[i], max);
        }

        int result = 0;
        for(int i =0 ;i<prices.length;i++){
            result = Math.max(left[i]+right[i],result);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] ints ={3,3};
        int i = new Solution().maxProfit(ints);
        System.out.println(i);
    }
}
